package main.leetcode.primary.from001to100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 18.四数之和
 *
 * <p>给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ， 使得 a + b + c +
 * d 的值与 target 相等？ 找出所有满足条件且不重复的四元组。
 *
 * <p>注意：答案中不可以包含重复的四元组。
 *
 * <p>示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 *
 * <p>满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex18 {
    public static void main(String[] args) {
        int[] nums = {0, 0, 0, 0};
        System.out.println(fourSum(nums, 0));
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        int i, j, k, h;
        int min, max, res;
        for (i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 略过重复nums[i]
            min = nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3];
            if (target < min) break; // 当前最小值大于目标值越往后越大，所以不存在了，break
            max = nums[n - 1] + nums[n - 2] + nums[n - 3] + nums[i];
            if (max < target) continue; // 当前最大值小于目标值，则需要增大nums[i]，continue

            for (j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 略过重复nums[j]
                min = nums[i] + nums[j] + nums[j + 1] + nums[j + 2];
                if (target < min) break; // 当前最小值大于目标值越往后越大，所以不存在了，break
                max = nums[n - 1] + nums[n - 2] + nums[j] + nums[i];
                if (max < target) continue; // 当前最大值小于目标值，则需要增大nums[i]，continue
                k = j + 1;
                h = n - 1;
                while (k < h) {
                    res = nums[i] + nums[j] + nums[h] + nums[k];
                    if (res < target) k++;
                    else if (res > target) h--;
                    else {
                        lists.add(Arrays.asList(nums[i], nums[j], nums[h], nums[k]));
                        while (k < h && nums[k] == nums[k + 1]) k++;
                        while (k < h && nums[h] == nums[h - 1]) h--;
                        k++;
                        h--;
                    }
                }
            }
        }
        return lists;
    }
}
